1. Field of the Invention
This invention relates to a high speed processor for converting spatial domain signals, such as video signals, into transformed domain representations with a Scaled Discrete Cosine Transform (SDCT) for use in performing image data compression. Likewise, this invention also discloses a high speed processor for use in performing image data decompression with Inverse Scaled Discrete Cosine Transform (ISDCT).
2. Description of the Related Art
Discrete Cosine Transform (DCT) is one of the most effective techniques for performing video data compression or video bandwidth compression. For example, the current international standards for image compression, the so-called Joint Photographic Experts Group (JPEG) and Motion Picture Coding Experts (MPEG), are based on the DCT method. It should be understood by one skilled in the art that video and image data are used interchangeably. In performing a DCT, the image is partitioned into many square blocks so that each block may be transformed individually. Currently, the JPEG and MPEG standards recommend that the block size be 8 pixels by 8 pixels. Each block may be transformed by one-dimensional DCT in the fashion of row by row followed by column by column. Subsequently, the DCT coefficients are quantized to filter high frequency components followed by an encoding process prior to transmission.
Nevertheless, the computational complexity in performing a DCT is the main concern in designing VLSI DCT chips because DCT imposes a stiff speed limitation for compressing high-definition video image in real time. For example, see U.S. Pat. Nos. 4,797,847 and 4,831,574. P. Duhamel and H'Mida showed in their paper, "New 2 n DCT Algorithms Suitable for VLSI Implementation," in Proceedings of IEEE International Conferences on Acoustics, Speech and Signal Processing (ICAASP-87), April 1987, Dallas, U.S.A., that the theoretical lower bound for implementing a one-dimensional 8-point DCT requires 11 multiplications. Recently, C. Loeffler, A. Lightenberg, and G. S. Moschytz presented a class of implementations for one-dimensional 8-point DCT using 11 multiplications in their paper, "Practical Fast One-dimensional DCT Algorithms with 11 Multiplications," in Proceedings of IEEE International Conferences on Acoustics, Speech and Signal Processing (ICAASP-88), 1989.
More recently, Y. Arai, T. Agui and M. Nakajima proposed that many of the DCT multiplications can be formulated as scaling multipliers to the DCT coefficients in their article, "A Fast DCT-SQ Scheme for Images," in Transactions of IEICE, Vol. E-71, No. 11, ppg. 1095-1097, November 1988. The DCT after the multipliers are factored out is called the Scaled DCT (SDCT). Evidently, the SDCT remains orthogonal as DCT but no longer normalized, while the scaling factors may be restored in the following quantization process. They have demonstrated that a one-dimensional 8-point SDCT needs only five multipliers, which is less than half of the theoretical lower bound for the corresponding DCT. E. Feig has mathematically described the SDCT, in particular the 8.times.8 SDCT, in the article, "Fast Scaled-DCT Algorithm," presented at the 1990 SPIE/SPSE Symposium of Electronic Imaging Science and Technology, 12 February 1990, Santa Clara, Calif., U.S.A., and a formal paper, "Fast Algorithms for the Discrete Cosine Transform," published in IEEE Transactions on Signal Processing, Vol. 40, No. 9, ppg. 2174-2193, September 1992.
However, the recursive properties of the SDCT have not been mentioned in all the previous publications. The recursive properties of DCT was first described by H. S. Hou in the article, "A Fast Recursive Algorithm for Computing the Discrete Cosine Transform," published in IEEE Transactions on Acoustics, Speech and Signal Processing, Vol. ASSP-35, No. 10, ppg. 1455-1461, October 1987. Subsequently, H. S. Hou presented the recursive properties of SDCT in the article, "Recursive Scaled-DCT," at the 1991 SPIE International Symposium, San Diego, Calif., U.S.A., appeared in conference proceedings 1567, ppg. 402-412, 22 Jul. 1991.
The recursive properties of SDCT allow one to implement a larger size SDCT using a combination of variants of smaller size SDCT. Consequently, in accordance with the invented architecture and the recursive SDCT algorithm presented in this application, a high throughput of image data compression and decompression is achieved with a relatively slow internal clock while minimizing the number of multipliers used in performing a larger size SDCT.